package simple;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2020/4/5 10:39
 */
public class No35_搜索插入位置 {
    public static void main(String[] args) {
        Solution35 solution35 = new Solution35();
        int[] nums = new int[]{5, 7, 12, 17, 19, 22};
        int[] targets = new int[]{3,7,18,25};
        //0,1,4,6
        for (int target : targets) {
            int i = solution35.searchInsert(nums, target);
            System.out.println(i);
        }
        System.out.println();
    }
}

class Solution35 {
    public int searchInsert(int[] nums, int target) {
        //二分查找 1-10000 6001 1-5000重复比较
        int red = 0;
        int green = nums.length - 1;
        int yellow = -1;
        while (red <= green) {
            yellow = (red + green) >>> 1;
            if (target > nums[yellow]) {
                red = yellow + 1;
            } else if (target < nums[yellow]) {
                green = yellow - 1;
            } else {
                return yellow;
            }
        }
        return red;
    }
}

    //public int searchInsert(int[] nums, int target) {
    //    for (int i = 0; i < nums.length; i++) {
    //        if (target <= nums[i]) {
    //            return i;
    //        }
    //    }
    //    return nums.length;
    //}